|
In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques.〔, definition 2.6.2, p.34; .〕 Trivially perfect graphs were first studied by but were named by ; Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees,〔; .〕 arborescent comparability graphs,〔.〕 and quasi-threshold graphs.〔.〕 ==Equivalent characterizations== Trivially perfect graphs have several other equivalent characterizations: *They are the comparability graphs of rooted forests. That is, if ''P'' is the partial order formed by the reachability relationship between vertices in a rooted forest, then the comparability graph of ''P'' is trivially perfect, and every trivially perfect graph can be formed in this way.〔, theorem 6.6.1, p. 99; , corollary 4.〕 *They are the graphs that do not have a ''P4'' path graph or a ''C4'' cycle graph as induced subgraphs.〔, theorem 6.6.1, p. 99; , theorem 2. and proved this for comparability graphs of rooted forests.〕 *They are the graphs that can be represented as the interval graphs for a set of nested intervals. A set of intervals is nested if, for every two intervals in the set, either the two are disjoint or one contains the other.〔, p. 51.〕 *They are the graphs that are both chordal and cographs.〔 This follows from the characterization of chordal graphs as the graphs without induced cycles of length greater than three, and of cographs as the graphs without induced paths on four vertices (''P4''). *They are the graphs that are both cographs and interval graphs.〔, p. 248; , theorem 3.〕 *They are the graphs that can be formed, starting from one-vertex graphs, by two operations: disjoint union of two smaller trivially perfect graphs, and the addition of a new vertex adjacent to all the vertices of a smaller trivially perfect graph.〔; .〕 These operations correspond, in the underlying forest, to forming a new forest by the disjoint union of two smaller forests and forming a tree by connecting a new root node to the roots of all the trees in a forest. *They are the graphs in which, for every edge ''uv'', the neighborhoods of ''u'' and ''v'' (including ''u'' and ''v'' themselves) are nested: one neighborhood must be a subset of the other.〔, theorem 3.〕 *They are the permutation graphs defined from stack-sortable permutations.〔.〕 *They are the graphs with the property that in each of its induced subgraphs the clique cover number equals the number of maximal cliques. *They are the graphs with the property that in each of its induced subgraphs the clique number equals the pseudo-Grundy number. *They are the graphs with the property that in each of its induced subgraphs the chromatic number equals the pseudo-Grundy number. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Trivially perfect graph」の詳細全文を読む スポンサード リンク
|